package quicksort;
//快速排序
import sun.text.CollatorUtilities;

import java.util.Random;

public class sort04 {
    public static int num=1;
    public static void main(String[] args) {
        Random random = new Random();
        int[] b = new int[10];
        for (int i = 0; i < b.length; i++) {
            b[i] = random.nextInt(100);
        }
        for (int  i :b) {
            System.out.print(i+"   ");
        }
        System.out.println();
        sort(b,0,b.length-1);
        System.out.println("最终结果：");
        for (int ints :b) {
            System.out.print(ints+"   ");
        }

    }
    public static void sort(int [] a,int low,int high)
    {
        if(low<high) {
            int p = partition(a, low, high);
            //System.out.println("第"+(num++)+"次和标杆交换的位置："+p);
//            for (int ints :a) {
//                System.out.print(ints+"   ");
//            }
            //System.out.println();
            sort(a, low, p - 1);
            sort(a, p + 1, high);
        }
    }
    public static int partition(int [] a,int low,int high)
    {
        int x=a[low];//设立标杆
        int i=low;
        int j=high+1;
        while(true)
        {
            while(i<high&&a[++i]<x);
            while(a[--j]>x);
            if(i>=j)
                break;
            change(a,i,j);
        }
        change(a,low,j);
        return j;
    }
    public static void change(int []a,int i,int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}
